package JZOffer;

public class _16 {
    class Solution {
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            if (root1 == null || root2 == null) return false;
            return isSubtree(root1,root2) ||
                    HasSubtree(root1.left,root2) ||
                    HasSubtree(root1.right,root2);
        }

        boolean isSubtree(TreeNode root1,TreeNode root2) {
            if (root2 == null) return true;
            if (root1 == null) return false;
            if (root2.val == root1.val) {
                return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
            }else return false;
        }
    }

    Solution getSolution() {
        return new Solution();
    }

    public static void main(String args[]) {
        _16 c = new _16();
        _16.Solution s = c.getSolution();
        TreeNode L1 = new TreeNode(3);
        TreeNode L2 = new TreeNode(4);
        TreeNode L3 = new TreeNode(5);
        TreeNode L4 = new TreeNode(6);
        TreeNode L5 = new TreeNode(7);
        L1.left = L2;
        L1.right = L3;
        L2.left = L4;
        L2.right = L5;
        TreeNode R1 = new TreeNode(4);
        TreeNode R2 = new TreeNode(6);
        TreeNode R3 = new TreeNode(7);
        R1.left = R2;
        R1.right = R3;

        System.out.println(s.HasSubtree(L1,R1));

    }
}
